package com.sheng.leetcode.year2022.month05.day18;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/05/18
 *
 * 668. 乘法表中第k小的数
 *
 * 几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
 * 给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。
 *
 * 例 1：
 *
 * 输入: m = 3, n = 3, k = 5
 * 输出: 3
 * 解释:
 * 乘法表:
 * 1	2	3
 * 2	4	6
 * 3	6	9
 * 第5小的数字是 3 (1, 2, 2, 3, 3).
 * 例 2：
 *
 * 输入: m = 2, n = 3, k = 6
 * 输出: 6
 * 解释:
 * 乘法表:
 * 1	2	3
 * 2	4	6
 * 第6小的数字是 6 (1, 2, 2, 3, 4, 6).
 * 注意：
 *
 * m 和 n 的范围在 [1, 30000] 之间。
 * k 的范围在 [1, m * n] 之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0668 {

    @Test
    public void test01(){
//        int m = 3, n = 3, k = 5;
        int m = 2, n = 3, k = 6;
        System.out.println(new Solution().findKthNumber(m, n, k));
    }

}
class Solution {
    public int findKthNumber(int m, int n, int k) {
        //暴力破解，计算出所有的值，然后排序二分查找------超时，寄
        int left = 1;
        int right = m * n + 1;
        //二分查找
        while(left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            // 统计每一行中小于mid的数字数量
            for(int i = 1; i <= m; i++) {
                count += Math.min(mid / i, n);
            }
            if(count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}

//思路
//对一个数值范围在[1,m * n]的矩阵，每一行从左到右是递增的，每一列从上到下是递增的。
//所以我们可以定义左右指针指向矩阵的初始和末尾，同时对每一次计算出的mid，累加矩阵中每一行，小于mid的元素个数cnt。
//
//如果最终cnt >= k，说明小于二分出的中间节点mid的元素个数比题目要求的k还要多，需要调整右指针r的位置，使其下一轮在[l, mid]中搜索；
//反之说明小于mid的元素个数比k要少，达不到k，需要调整左指针l的位置，使其下一轮在[mid + 1, r]中搜索。
//重点说明的是：如何统计每一行中小于mid的数，我们使用的是Math.min(mid / i, n)，来统计每一行的个数。
//解释：mid / i， 就是使用mid 除以 行号，即为用mid除以一个乘数(行)，得到另一个乘数(列)，
//这个列所在的位置及其之前的数，都是小于等于mid的数，累加列数即可；
//特别的如果 mid / n > n，即mid很大，除完之后发现超出了列数，所以说明这一行都是小于mid的，累加mid即可
//class Solution {
//    public int findKthNumber(int m, int n, int k) {
//        int left = 1;
//        int right = m * n + 1;
//        while(left < right) {
//            int mid = left + (right - left) / 2;
//            int count = 0;
//            // 统计每一行中小于mid的数字数量
//            for(int i = 1; i <= m; i++) {
//                count += Math.min(mid / i, n);
//            }
//            if(count >= k) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return right;
//    }
//}
//————————————————
//版权声明：本文为CSDN博主「永远在摸鱼的桃」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
//原文链接：https://blog.csdn.net/Amxrjgcs/article/details/124835865

//三叶佬
//二分 + 计数判定
//由于 n 和 m 的数据范围都是 3 * 10^4，总数本身就超过了 10^7 ，我们考虑线性复杂度往下的对数复杂度。
//题目要求我们求一维展开有序序列中的第 k 小的数，问题本身具有「二段性」：
//答案右边的每个数均 满足「其在一维展开有序序列中左边数的个数大于等于 k 个」
//答案左边的每个数均 不满足「其在一维展开有序序列中左边数的个数大于等于 k 个」
//我们考虑如何进行「二分答案」: 假设当前我们二分到的值是 mid，对于乘法表中的每行和每列均是单调递增，我们可以通过累加统计 每行/每列 中比 mid 小的数，
//记作 a，累加统计 每行/每列 中等于 mid 的数，记作 b，那么 cnt = a + b 即是整个乘法表中小于等于 mid 的数的个数，再通过 cnt 和 k 的大小关系来指导左右指针的变化。
//具体的，假设我们通过枚举行来统计 a 和 b，当前枚举到的行号为 i（行号从 1 开始），该行的最大数为 i * m：
//若 i * m < mid，整行都是小于 mid 的数，直接在 a 基础上累加 m；
//若 i * m >= mid，根据 mid 是否存在于该行进行分情况讨论：
//mid 能够被 i 整除，说明 mid 存在于该行，那么比 mid 小的数的个数为 mid/i - 1，将其累加到 a，同时对 b 进行加一；
//mid 不能够被 i 整除，说明 mid 不存在于该行，那么比 mid 小的数的个数为 mid/i ，将其累加到 a。
//一些细节：由于乘法表具有对称性，我们统计时可以对 行和列 中较小的一方进行遍历。
//
//代码：
//
//Java
//
//class Solution {
//    int n, m, k;
//    public int findKthNumber(int _m, int _n, int _k) {
//        n = Math.min(_m, _n); m = Math.max(_m, _n); k = _k;
//        int l = 1, r = m * n;
//        while (l < r) {
//            int mid = l + r >> 1, cnt = getCnt(mid);
//            if (cnt >= k) r = mid;
//            else l = mid + 1;
//        }
//        return r;
//    }
//    int getCnt(int mid) {
//        int a = 0, b = 0;
//        for (int i = 1; i <= n; i++) {
//            if (i * m < mid) {
//                a += m;
//            } else {
//                if (mid % i == 0 && ++b >= 0) a += mid / i - 1;
//                else a += mid / i;
//            }
//        }
//        return a + b;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solution/by-ac_oier-7pmt/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
